#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 物品结构体类型 
struct Goods	
{
	int no;	// 物品的编号
	int w;	// 物品的重量
	int v;	// 物品的价值
	
	// 构造函数
	Goods(int no1,int w1,int v1)	
	{
		no=no1;
		w=w1;
		v=v1;
	}
	
	// 用于按v/w递减排序 -- 单位价值
	bool operator<(const Goods&s) const
	{
		return (double)v/w > (double)s.v/s.w;
	}
};

int n = 4; // 4种物品
int W = 6; // 背包容量为6

// 4种物品
vector<Goods> g={Goods(0,5,4), Goods(1,3,4), Goods(2,2,3), Goods(3,1,1)};

// 存放最优解向量
vector<int> bestx;

// 存放最大价值,初始为0
int bestv = 0;

// 输出最优解
void disp()
{
	printf("最佳装填方案\n");
	for (int i=0;i<n;i++)
		if (bestx[i]==1)
			printf("  选取第%d个物品\n",g[i].no);
	printf("  总重量=%d,总价值=%d\n",W,bestv);
}

// 计算第i层结点的上界函数值
double bound(int cw, int cv, int i)
{
	// 背包的剩余容量
	int rw = W-cw;	
	
	// 表示物品价值的上界值
	double b=cv;
	int j=i;
	while (j<n && g[j].w<=rw)
	{
		rw-=g[j].w;	// 选择物品j
		b+=g[j].v;	// 累计价值
		j++;
	}
	
	// 最后物品只能部分装入
	if (j < n)
		b += (double)g[j].v/g[j].w*rw;
	return b;
}

// 累计搜索的结点个数
int sum = 0;

// 回溯算法
void dfs(int cw, int cv, vector<int>&x, int i)
{
	sum++;
	printf("[%d,%d]\n", cw, cv);
	
	// 找到一个叶子结点
	if (i >= n)
	{
		printf("找到一个解[%d,%d]\n",cw,cv);
		
		// 找到一个满足条件的更优解,保存它
		if (cw<=W && cv>bestv)
		{
			bestv=cv;
			bestx=x;
		}
	}
	
	// 没有到达叶子结点
	else
	{
		// 左剪支
		if(cw+g[i].w <= W)
		{ 
			x[i]=1; // 选取物品i
			dfs(cw+g[i].w,cv+g[i].v,x,i+1);
		}
		else
			printf("左剪支[%d,%d]\n",cw+g[i].w,cv+g[i].v);
		
		// 右剪支
		double b=bound(cw,cv,i+1);
		if(b > bestv)
		{
			printf("扩展右孩子结点b=%g\n", b); 
			x[i]=0; // 不选取物品i 
			dfs(cw, cv, x, i+1);
		}
		else
			printf("右剪支[%d,%d],b=%g\n",cw,cv,b);
	}
}

// 输出物品信息：编号、重量、价值、单位价值
void dispg()
{
	for(int i=0; i<g.size(); i++)
		printf("%d\t%d\t%d\t%g\n", g[i].no, g[i].w, g[i].v, (double)g[i].v/g[i].w);
}

// 求0/1背包问题
void knap()
{
	// 存储解向量
	bestx.resize(n);
	vector<int> x(n);
	
	// 物品按单位价值排序
	sort(g.begin(), g.end());
	printf("sort\n"); dispg();
	
	// i从0开始
	dfs(0, 0, x, 0);
	
	// 输出最优解
	disp();
}

int main()
{
	// 输出物品信息
	printf("g:\n"); dispg();
	
	// 求0/1背包问题
	knap();
	
	// 输出最大装载价值
	printf("sum=%d\n", sum);
	return 0;
}
